import Stack from "@/sources/Stack/useSl";
import { IIterator } from "@/sources/types";
import { Tree } from "../base";
import { print } from './test'
import { AVLNode } from "./types";


/**
 * 二叉搜索树
 */
export default class BST<T = number> extends Tree<T> {
    private sizes = 0;
    private root: AVLNode<T> | null
    // 默认的比较器
    private comparator = (a: T, b: T) => ((a as any) - (b as any))
    constructor(comparator?: (a: T, b: T) => number) {
        super();
        this.root = null
        comparator && (this.comparator = comparator);
    }

    /**
     * 获取根节点
     */
    getRoot() {
        return this.root;
    }

    /**
     * 节点的数量
     */
    size() {
        return this.sizes;
    }

    /**
     * 是否为空
     */
    isEmpty() {
        return this.sizes === 0
    }

    /**
     * 清空二叉树
     */
    clear() {
        // 清空根节点和sizes置为空即可
        this.sizes = 0;
        this.root = null
    }

    /**
     * 添加节点
     * @param element 
     */
    add(element: T) {
        // 首次添加
        if (this.root === null) {
            this.root = new AVLNode(element, null, null, null);
            this.sizes++;
            return;
        }

        // 找到要插入的节点
        let root = this.root;
        let prevNode: AVLNode<T> | null,
            isRight = false;
        while (root) {
            // 保存这次的节点
            prevNode = root;
            if (this.comparator(element, root.value!) > 0) {
                // 往右边找
                root = root.right!;
                isRight = true
            } else if (this.comparator(element, root.value!) < 0) {
                // 往左边找
                root = root.left!
                isRight = false;
            } else {
                // 相等，直接更新节点的值
                root.value = element
                // 直接返回
                return;
            }
        }

        // 到这prevNode就是要找的插入的节点

        const newNode = new AVLNode(element, prevNode!, null, null)

        // 判断插入左还是右
        if (isRight) {
            // 插入 prevNode的右边
            prevNode!.right = newNode
        } else {
            // 插入prevNode的左边
            prevNode!.left = newNode
        }

        // 添加后调整高度
        this.afterAdd(newNode);


        this.sizes++;
    }

    /**
      * 中序遍历(非递归)
      * @param node 
      */
    inOrder(iterator: (ele: T) => void, node = this.root) {
        if (node === null) return;
        // 创建一个栈
        const stack = new Stack<AVLNode<T>>()

        // 1. 开始时node为根节点，进入循环
        // 2. 最左节点为空，栈中还有值
        // 3. 栈为空了，开始遍历右边
        while (node === this.root || !stack.isEmpty() || node !== null) {
            // 从node开始一直遍历到最左边
            while (node !== null) {
                stack.push(node);
                node = node.left;
            }
            // 最左边为空， 开始取出最左边的节点开始访问
            node = stack.pop()!;
            // 访问节点
            iterator(node.value!)
            // 访问节点的右节点
            node = node.right;
        }
    }

    /**
     * 添加节点之后进行调整
     * @param newNode 
     */
    afterAdd(node: AVLNode<T>) {
        // if (node.value as any  === 7) debugger
        // debugger
        // 更新祖先节点的高度， 一旦添加就更新组先节点的高度
        while ((node = node.parent!) !== null) {
            // 当前父节点平衡
            if (node.isBalance()) {
                // 更新该节点的高度
                node.updateHeight();
            } else {
                // 当前父节点不平衡

                // 恢复平衡
                this.reBanlance2(node)

                // 恢复了最近的不平衡的组先，上面的组先都会平衡
                break;
            }

        }
    }

    /**
     * 统一所有的旋转
     */
    reBanlance2(grand: AVLNode<T>) {
        // 判断各种类型的失衡, LL, RR, LR, RL
        let parent = grand.getTallChild()!,
            node = parent?.getTallChild()!;
        const toBalance = (r: AVLNode<T>, b: AVLNode<T>, c: AVLNode<T> | null, d: AVLNode<T>, e: AVLNode<T> | null, f: AVLNode<T>) => {
            // 更改parent
            d.parent = r.parent

            // 更改原来parent的指向
            if (r.isLeft()) {
                r.parent!.left = d;
            } else if (r.isRight()) {
                r.parent!.right = d
            } else {
                // 是根
                this.root = d;
            }

            // b-c
            b.right = c;
            if (c !== null) {
                c.parent = b;
            }
            b.updateHeight();

            // e-f
            f.left = e;
            if (e !== null) {
                e.parent = f;
            }

            f.updateHeight();

            // d-f-d
            d.left = b;
            d.right = f;
            if (b !== null) {
                b.parent = d
            }
            if (f !== null) {
                f.parent = d;
            }
            // 更新父节点的高度
            d.updateHeight()
        }

        if (parent.isLeft()) { // 确定是 L
            // 是grand的左节点

            if (node.isLeft()) { // LL型 右旋
                toBalance(grand, node, node.right, parent, parent.right, grand)

            } else { // LR型
                toBalance(grand, parent, node.left, node, node.right, grand)
            }


        } else { // 确定是R
            // 是grand的右节点

            if (node.isRight()) { // RR型
                // 左旋
                toBalance(grand, grand, parent.left, parent, node.left, node)
            } else { // RL型
                toBalance(grand, grand, node.left, node, node.right, parent)
            }
        }
    }



    /**
     * 恢复平衡
     * @param node 
     */
    reBanlance(grand: AVLNode<T>) {
        // 判断各种类型的失衡, LL, RR, LR, RL
        let parent = grand.getTallChild()!,
            node = parent?.getTallChild()!;

        if (parent.isLeft()) { // 确定是 L
            // 是grand的左节点

            if (node.isLeft()) { // LL型 右旋
                this.rotateRight(grand)
            } else { // LR型
                // 先左旋，再右旋
                this.rotateLeft(parent)
                // 现在node已经变成了 parent
                this.rotateRight(grand)
            }


        } else { // 确定是R
            // 是grand的右节点

            if (node.isRight()) { // RR型
                // 左旋
                this.rotateLeft(grand)
            } else { // RL型
                // 先右旋，再左旋
                this.rotateRight(parent)
                this.rotateLeft(grand)
            }
        }
    }

    /**
     * 处理旋转之后父节点的指向以及更新高度
     * @param grand 
     * @param par 
     */
    private afterRotate(grand: AVLNode<T>, par: AVLNode<T>) {
        // grand原来是左孩子还是右孩子， 先保存起来，后面判断会失误(grand的父亲已经改了)
        const isLeftChild = grand.isLeft();
        // 更新parent
        par.parent = grand.parent
        grand.parent = par;

        // 更改parent的指向
        if (par.parent === null) {
            this.root = par
        } else {
            // 原来grand的父元素不为空
            if (isLeftChild) {
                // 原来是左孩子
                par.parent.left = par
            } else {
                // 原来是右孩子，更改右孩子
                par.parent.right = par
            }
        }
        // 更新高度(注意的是先更新grand的高度，再更新parent的高度)
        grand.updateHeight()
        par.updateHeight()
    }

    /**
     * 右旋
     * @param grand 
     * @param par 
     */
    rotateRight(grand: AVLNode<T>) {
        let par = grand.left!;

        grand.left = par.right;
        par.right = grand;

        // 更新par.right的parent, 现在已经变成grand.left
        if (grand.left !== null) {
            grand.left.parent = grand
        }
        // 处理旋转之后
        this.afterRotate(grand, par)
    }

    /**
     * 左旋
     * @param grand 
     * @param par 
     */
    rotateLeft(grand: AVLNode<T>) {
        const par = grand.right!;

        grand.right = par.left;
        par.left = grand;

        // 更新par.left的parent
        if (grand.right !== null) {
            grand.right.parent = grand;
        }

        // 处理旋转之后
        this.afterRotate(grand, par)
    }



    /**
     * 获取element
     * @param element 
     */
    private get(element: T) {
        let root = this.root!;
        while (root !== null) {
            if (this.comparator(element, root.value!) > 0) {
                root = root.right!;
            } else if (this.comparator(element, root.value!) < 0) {
                root = root.left!;
            } else {
                // 找到了
                return root
            }
        }
        // 循环下来都没有找到
        return null
    }

    /**
     * 删除节点
     * @param element 
     */
    remove(element: T) {
        let node = this.get(element);
        // 要删除的节点不存在
        if (node === null) return null

        // 删除度为2的节点, 找到其前驱或者后继节点， 这里使用前驱节点
        if (node.hasTwoChild()) {
            // 1. 获取node节点的前驱节点
            const accesssor = this.accessor(node);

            // 2. 使用前驱节点替换要删除的该节点
            node.value = accesssor!.value

            // 3. 删除该前驱节点, 跟删除度为1和度为2的节点一样
            node = accesssor
        }

        // 判断该节点是父元素的左孩子还是右孩子
        const isLeft = node!.isLeft() ? true : false
        // 删除度为1的节点
        if (node?.hasOneChild()) {
            // 节点的孩子是左还是右
            const hasLeftChild = node.hasLeftChild();
            // 找到替换的节点
            const replacement = (hasLeftChild ? node.left : node.right)!;
             // 该节点是跟节点
             if (node.parent == null) {
                this.root = replacement
            } else {
                if (isLeft) {
                    node.parent!.left = replacement
                } else {
                    node.parent!.right = replacement
                }
            }
            
            // 更新父节点
            replacement.parent = node.parent
            this.afterRemove(node)
        } else if (node!.parent === null) {
            // 删除的是根节点
            this.root = null
        }
        else {
            // 度为0的节点
            if (isLeft) {
                // 是父节点的左孩子
                node!.parent!.left = null
            } else {
                // 是父节点的右孩子
                node!.parent!.right = null
            }
            this.afterRemove(node!)
        }
        // 长度减一
        this.sizes--;

    }

    /**
     * 删除节点之后调节平衡
     */
    afterRemove(node: AVLNode<T>) {
        while ((node = node.parent!) !== null) {
            // 平衡
            if (node.isBalance()) {
                // 更新高度
                node.updateHeight();
            } else {
                // 更新平衡，因为平衡导致组先节点都会失衡，要一直调节失衡
                this.reBanlance(node);
            }
        }
    }

    /**
     * 后继节点
     * 从根节点的右节点开始，不断找该右节点的左节点
     */
    successor(root: AVLNode<T>) {
        // 树是空的
        if (this.isEmpty()) return null;
        let node = root?.right;
        // 没有右节点
        if (node === null) return null;

        while (node!.left !== null) {
            node = node?.left;
        }
        return node;
    }

    /**
     * 前继节点
     * 从根节点的左节点开始，不断找该左节点的右节点
     */
    accessor(root: AVLNode<T>) {
        if (this.isEmpty()) return null;
        let node = root?.left;
        // 没有左节点
        if (node === null) return null;

        while (node!.right !== null) {
            node = node?.right;
        }
        return node;
    }




    /**
     * 是否包含元素
     * @param element 
     */
    contains(element: T) {
        if (this.isEmpty()) return false
        return this.get(element) !== null;
    }

    /**
     * 批量添加
     * @param eles 
     */
    batchAdd(eles: Array<T>) {
        eles.forEach(ele => {
            this.add(ele)
            print(this)
        })
    }

    /**
     * 批量删除
     * @param elem 
     */
    batchRemove(eles: Array<T>) {
        eles.forEach(ele => {
            this.remove(ele)
            print(this)
        })
    }


} 